import java.util.*;

import util.VectorUtils;

public class RPTree
{
	class RPNode extends NN
	{
		private Point splitter;
		private RPNode left;
		private RPNode right;
		private int dimension;
		private boolean isLeaf;
		private double median;
		private Integer[] dict; 
		private int iterateCounter;
		
		public RPNode(Point DataBase[], int dimension, Integer[] dict)
		{
			super(DataBase);
			this.dimension = dimension;
			this.iterateCounter = 0;
			this.dict = dict;
			
			isLeaf = false;
			if (DataBase.length <= 5) 
			{
				isLeaf = true;
				return;
			}

			createSplitter();

			SortingElement productArray[] = getProduct(DataBase, splitter);

			// Determine which points go to which node
			ArrayList<Point> LeftData = new ArrayList<Point>();
			ArrayList<Point> RightData = new ArrayList<Point>();
			for (int i = 0; i < pointCount; i++)
			{
				if (productArray[i].value < median) LeftData.add(DataBase[i]);
				else RightData.add(DataBase[i]);
			}

			// Determine what to do if it's a bad split (either child has 0 point)
			if ((LeftData.size() == 0) || (RightData.size() == 0))
			{
				// Repeat the procedure by choosing new random vector if it's a bad split
				while(((LeftData.size() == 0) || (RightData.size() == 0)) && (iterateCounter < 10))
				{
					createSplitter();

					productArray = getProduct(DataBase, splitter);

					LeftData = new ArrayList<Point>();
					RightData = new ArrayList<Point>();
					for (int i = 0; i < pointCount; i++)
					{
						if (productArray[i].value < median) LeftData.add(DataBase[i]);
						else RightData.add(DataBase[i]);
					}
					iterateCounter++;
					System.out.println(iterateCounter + "," + pointCount);
				}
				isLeaf = true;
				return;
			}

			left = new RPNode(LeftData.toArray(new Point[LeftData.size()]), dimension, dict);
			right = new RPNode(RightData.toArray(new Point[RightData.size()]), dimension, dict);
		}

		private void createSplitter()
		{
			Random randomizer = new Random();
			HashMap<Object, Double> featureSparse = new HashMap<Object, Double>();
			Double len = 0.0;
			for (int i = 0 ; i < dimension ; i++)
			{
				// Now use only gaussian random
				Double nextRandom = randomizer.nextGaussian();
				featureSparse.put(dict[i], nextRandom);
				len += Math.pow(nextRandom, 2);
			}
			// Normalize to unit vector
			featureSparse = (HashMap<Object, Double>)VectorUtils.ScalarMultiply(featureSparse, 1d / len);

			splitter = new Point(-1, featureSparse, DataBase[0].type());
		}

		// Dot product of points in database and a random unit vector
		public SortingElement[] getProduct(Point DataBase[], Point splitter)
		{
			SortingElement[] arr = new SortingElement[pointCount];
			for (int i = 0 ; i < pointCount; i++)
			{
				arr[i] = new SortingElement(i, VectorUtils.DotProduct(DataBase[i].FeatureSparse(), splitter.FeatureSparse()));
			}
			SortingElement[] arrCpy = new SortingElement[pointCount];
			System.arraycopy(arr, 0, arrCpy, 0, pointCount); 
			Arrays.sort(arrCpy);
			median = arrCpy[pointCount/2].value;
			
			return arr;
		}

		public NN.SortingElement[] Query(Point q)
		{
			SortingElement[] retVal = new SortingElement[1];
			Point best = Query(q, DataBase[0]);
			retVal[0] = new NN.SortingElement(best.ID(), best.Distance(q));
			return retVal;
		}

		public Point Query(Point q, Point best)
		{
			
			if (isLeaf)
			{
				Double bestDist = q.Distance(best);
				for (int i = 0; i < pointCount; i++)
				{
					Double x = q.Distance(DataBase[i]);
//					System.out.println(DataBase[i].ID());
					if (x < bestDist)
					{
						bestDist = x;
						best = DataBase[i];
//						System.out.println("best Now : " + best.ID() + ", score : " + best.Distance(q));
					}
				}
				return best;			
			}
			
			Double x = VectorUtils.DotProduct(splitter.FeatureSparse(), q.FeatureSparse());
			if (x < median) best = left.Query(q, best);
			else best = right.Query(q, best);

			return best;
		}
	}

	RPNode root;
	Point[] DataBase;

	public RPTree(Point DataBase[], int dimension, Integer[] dict)
	{
		this.DataBase = DataBase;
		root = new RPNode(DataBase, dimension, dict);
	}

	public NN.SortingElement[] Query(Point q)
	{
		return root.Query(q);
	}
}
